//
// Created by 紫霄 on 2020/3/22.
//

#ifndef CPP_DEMO_TEST_H
#define CPP_DEMO_TEST_H

#include <iostream>
#include <list>
#include <string>
#include <vector>
//#include <cstdlib>
using namespace std;

// 二分法查找
size_t positionInArray(const double *Array, int lengthArray,
                       double toFindNumbers);

size_t positionInArray(const double *Array, int lengthArray,
                       double toFindNumbers) {
  int beg = 0, end = lengthArray;
  auto mid = (beg + end) / 2;
  if (Array[0] > Array[1]) { //假如是降序排列
    while (beg <= end) {
      // 此处优先判断向左，因为向左或者是向右的概率大于相等的概率；
      if (Array[mid] > toFindNumbers) {
        beg = mid + 1;         // begin 需要mid + 1 操作
        mid = (beg + end) / 2; // fibnacci 查找的话 需要将/2 变为 乘以 0.618
      } else if (toFindNumbers > Array[mid]) {
        end = mid; // end 不需要 end + 1 操作
        mid = (beg + end) / 2;
      } else
        return mid;
    }
  } else { //假如是生序
    while (beg <= end) {
      if (toFindNumbers < Array[mid]) {
        end = mid;
        mid = (beg + end) / 2;
      } else if (Array[mid] < toFindNumbers) {
        beg = mid + 1;
        mid = (beg + end) / 2;
      } else {
        return mid;
      }
    }
  }
  return 0;
}

// 最优二分查找
int bestFind(double *a, size_t length, double theNum) {
  size_t beg = 0, end = length;
  while (beg < end) {
    size_t mid = (beg + end) >> 1; // 右移操作，右移几就是2的几次方；
    (theNum < a[mid]) ? end = mid : beg = mid + 1;
  }
  return --beg;
}

// 简单排序
void simpleSorting(double Array[], size_t lengthArray) {
  // 一共要进行的次数，从第一个元素开始
  for (size_t cnt = 0; cnt < lengthArray; ++cnt) {
    size_t smallestIndex = cnt;
    // 找到位于后续序列的最小值
    for (size_t index = cnt + 1; index < lengthArray; ++index) {
      if (Array[smallestIndex] > Array[index]) {
        smallestIndex = index;
      }
    }
    double temp = Array[cnt];
    Array[cnt] = Array[smallestIndex];
    Array[smallestIndex] = temp;
  }
}

// 快速排序 使用vector 从小到大
void quickSort(size_t arrLeft, size_t arrRight, vector<double> &array) {
  if (arrLeft >= arrRight) {
    return;
  }
  size_t i = arrLeft, j = arrRight;
  double base = array[arrLeft], temp;
  while (i < j) {
    while (array[j] >= base && i < j) {
      --j;
    }
    while (array[i] <= base && i < j) {
      ++i;
    }
    if (i < j) {
      temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    }
  }
  temp = array[i];
  array[i] = base;
  array[arrLeft] = temp;
  quickSort(arrLeft, i - 1, array);
  quickSort(i + 1, arrRight, array);
}

//  !! 归并排序 !!
// 先定义一个merge函数，用来讲两个有序数组合为一个有序数组(主要逻辑)
void merge(double *a, size_t beg, size_t mid, size_t end) {
  //    auto *B = (double *)malloc((mid - beg)*(sizeof(double)));
  auto *B = new double[mid - beg];
  double *A = a + beg;
  double *C = a + mid;
  auto lb = mid - beg;
  auto lc = end - mid;
  for (size_t j = 0, i = beg; j < lb; ++j) {
    B[j] = a[i];
    ++i;
  }
  for (size_t i = 0, j = 0, k = 0; j < lb;) {
    if ((k < lc) && (C[k] <= B[j]))
      A[i++] = C[k++];
    if ((lc <= k) || (B[j] < C[k]))
      A[i++] = B[j++];
  }
  delete[] B;
}

// 定义主函数
void mergeSort(double *a, size_t beg, size_t end) {
  if ((end - beg) < 2)
    return;
  size_t mid = (beg + end) >> 1;
  mergeSort(a, beg, mid);
  mergeSort(a, mid, end);
  merge(a, beg, mid, end);
}

//  冒泡排序 从小到大 for 循环
void bubbleSort(double *Array, size_t n) {
  // 此处需要用 !sorted, 使用true会错误, 此处条件好好理解！！
  for (bool sorted = false; sorted = !sorted; n--) {
    sorted = true;
    for (size_t k = 0; k < n - 1; ++k) {
      if (Array[k] > Array[k + 1]) {
        swap(Array[k], Array[k + 1]);
        sorted = false;
      }
    }
  }
}

// 冒泡拍秀 while 循坏
void bubbleSort2(double *Array, size_t n) {
  bool sorted = false;
  while (!sorted) {
    sorted = true;
    for (size_t i = 0; i < n - 1; ++i) {
      if (Array[i] > Array[i + 1]) {
        swap(Array[i], Array[i + 1]);
        sorted = false;
      }
    }
    --n;
  }
}

// 于数组中取最大元素与次大元素
void max2(double *a, size_t low, size_t hi, double &max, double &secondMax) {
  if ((max = a[low]) < (secondMax = a[low + 1])) {
    swap(max, secondMax);
  }
  for (size_t i = low + 2; i < hi; ++i) {
    if (a[i] > secondMax) {
      secondMax = a[i];
      if (secondMax > max) {
        swap(secondMax, max);
      }
    }
  }
}

// 较慢的Fibonacci 数列  自顶而下 递归
int fib(int n) { return (n < 2) ? n : (fib(n - 2) + fib(n - 1)); }

// 还行的fibonacci 数列 迭代
long int fib2(long int n) {
  long int i = 0, j = 1;
  while (n--) {
    // i 为两者的和 即fib下一项
    i = i + j;
    // j 为 原i的值
    j = i - j;
  }
  return i;
}

// 公共子序列
// 实现逻辑，利用了递归，每次检查末字符，相同的话进行递归加一，否则分两种情况
// 即去掉其中一个字符串末尾后与另一串尚未去掉末尾字符的进行递归，取两种情况下的较高的值
int publicSubsequence(char *s1, char *s2, size_t len_1, size_t len_2) {
  if (len_1 - 1 == 0 || len_2 - 1 == 0) {
    return 0;
  }
  if (s1[len_1 - 2] == s2[len_2 - 2]) {
    return 1 + publicSubsequence(s1, s2, len_1 - 1, len_2 - 1);
  }
  int k = publicSubsequence(s1, s2, len_1, len_2 - 1);
  int j = publicSubsequence(s1, s2, len_1 - 1, len_2);
  if (k > j) {
    return k;
  }
  return j;
}

// 通过动态规划进行优化，将递归转为迭代

int publicSubsequence2(char *s1, char *s2, size_t len_1, size_t len_2) {
  int a_1[1000][1000] = {0}; //此处横纵序列均比char数组多一个元素 第0行第0列
  // TODO：此处待优化 动态数组无法初始化 可使用vector；
  for (size_t i = 1; i < len_1; ++i) {
    for (size_t j = 1; j < len_2; ++j) {
      if (s1[i - 1] == s2[j - 1]) {
        a_1[i][j] = a_1[i - 1][j - 1] + 1;
      } else {
        a_1[i][j] =
            (a_1[i - 1][j] > a_1[i][j - 1]) ? a_1[i - 1][j] : a_1[i][j - 1];
      }
    }
  }
  return a_1[len_1 - 1][len_2 - 1];
}

// 找到最小数的下标
int minIndex(const double *Array, size_t lengthArray) {
  size_t smallestIndex = 0;
  for (size_t index = 1; index < lengthArray; ++index) {
    if (Array[smallestIndex] > Array[index]) {
      smallestIndex = index;
    }
  }
  return smallestIndex;
}

void print(const int p[], size_t size) {
  for (size_t i = 0; i < size; ++i) {
    cout << p[i] << " ";
  }
  cout << endl;
}

// 简单排序
void simpleSorting(double (&Array)[], size_t lengthArray);

#endif // CPP_DEMO_TEST_H
